
#include "util.h"
#include "suffix_tree.h"

//--------------------explict specialization for wchar_t----------------
template<>
void SuffixTree<wchar_t>::insert(SuffixTreeNode<wchar_t> * cur, wchar_t * suffix)
{
	cur->counter++;
	if(type == SuffixTree<wchar_t>::RIGHT_SUFFIX_TREE && *(++suffix) != 0
		|| type == SuffixTree<wchar_t>::LEFT_SUFFIX_TREE && *(--suffix) != 0)
	{
		appendAsChildOrStringTail(cur, suffix);
	}else
	{
		cur->endWithNullCounter++;
	}
}

template<>
void SuffixTree<wchar_t>::travel(SuffixTreeNode<wchar_t> *node,wchar_t *prefix, int depth)
{
	wchar_t *str = new wchar_t[depth+1];
	wchar_t *next_pre = new wchar_t[depth];
	for(int i = 0; i <depth-1; ++i)
	{
		str[i] = prefix[i];
		next_pre[i] = prefix[i];
	}

	str[depth-1] = node->state;
	next_pre[depth-1] = node->state;
	str[depth] = 0;

	for(int i = 0; i < depth; i++)
		printf("  ");
	printf("prefix: ");
	print_wchar(str);
	
	for(int i = 0; i < depth; i++)
		printf("  ");
	printf("-level:%d, suffix:%d children:%d count:%d \n",depth,node->tailsSize,node->childrenSize,node->counter);
	
	AVL<wchar_t,wchar_t*>::Iterator<wchar_t,wchar_t *> iter(&node->tails);
	wchar_t key;
	wchar_t * item;
	bool more = iter.GetFirst(key,item);
	while(more)
	{
		for(int i = 0; i < depth; i++) printf("  ");
		printf("  ");
		if(type == SuffixTree<wchar_t>::RIGHT_SUFFIX_TREE)
			print_wchar(item);
		else
			print_wchar_reverse(item);
		printf("\n");

		more = iter.GetNext(key,item);
	}
	
	AVL<wchar_t,SuffixTreeNode<wchar_t> * >::Iterator<wchar_t,SuffixTreeNode<wchar_t>*> iter2(&node->children);
	wchar_t key2;
	SuffixTreeNode<wchar_t> * item2;
	bool more2 = iter2.GetFirst(key2,item2);
	while(more2)
	{
		this->travel(item2,next_pre,depth+1);
		more2 = iter2.GetNext(key2,item2);
	}

	delete [] str;
	delete [] next_pre;
}

template<>
void SuffixTree<wchar_t>::travel()
{
	printf("Total %d nodes.\n",countNodes(root,-1));
	printf("%d Words have been inserted.\n",countWordInserted(root));
	printf("-level:%d, suffix:%d children:%d\n",0,root->tailsSize,root->childrenSize);
	
	AVL<wchar_t,wchar_t*>::Iterator<wchar_t,wchar_t *> iter(&root->tails);
	wchar_t key;
	wchar_t * item;
	bool more = iter.GetFirst(key,item);
	while(more)
	{
		printf("  ");
		if(type == SuffixTree<wchar_t>::RIGHT_SUFFIX_TREE)
			print_wchar(item);
		else
			print_wchar_reverse(item);
		printf("\n");

		more = iter.GetNext(key,item);
	}
	AVL<wchar_t,SuffixTreeNode<wchar_t> * >::Iterator<wchar_t,SuffixTreeNode<wchar_t> *> iter2(&root->children);
	wchar_t key2;
	SuffixTreeNode<wchar_t> * item2;
	bool more2 = iter2.GetFirst(key2,item2);
	while(more2)
	{
		travel(item2,0,1);
		more2 = iter2.GetNext(key2,item2);
	}
}


template<>
void SuffixTree<wchar_t>::appendToPrefix(wchar_t * prefix, wchar_t state, wchar_t *newResult, int prefix_length)
{
	if(type == SuffixTree<wchar_t>::RIGHT_SUFFIX_TREE)
	{
		for(int i = 0; i < prefix_length; ++i)
		{
			newResult[i] = prefix[i];
		}
		newResult[prefix_length] = state;
	}
	else
	{
		newResult[0] = state;
		for(int i = 0; i < prefix_length; ++i)
		{
			newResult[i+1] = prefix[i];
		}
	}

}
template<>
void SuffixTree<wchar_t>::collectWordContext(SuffixTreeNode<wchar_t> *node, int parent_depth, wchar_t* prefix, int prefixLength, WordContext<wchar_t>* list,int& index)
{
	int depth = parent_depth+1;
	
	if(depth < minMumWordLength)
	{
		wchar_t * temp = new wchar_t[depth];
		appendToPrefix(prefix,node->state,temp,parent_depth);

		AVL<wchar_t, SuffixTreeNode<wchar_t> *>::Iterator<wchar_t, SuffixTreeNode<wchar_t> *> iter(&node->children);
		wchar_t key;
		SuffixTreeNode<wchar_t> *item;
		bool more = iter.GetFirst(key,item);
		while(more)
		{
			collectWordContext(item,depth, temp, depth, list,index);
			more = iter.GetNext(key,item);
		}
		delete [] temp;
	}
	else
	{
		WordContext<wchar_t> * ctx = &list[index++];

		//initial length
		ctx->length = depth;
		
		//initial str
		ctx->str = new wchar_t[depth];
		
		appendToPrefix(prefix,node->state,ctx->str, parent_depth);

		//remember current node reference
		ctx->treeNode = node;

		//travel to all node recursively
		AVL<wchar_t, SuffixTreeNode<wchar_t> *>::Iterator<wchar_t, SuffixTreeNode<wchar_t> *> iter(&node->children);
		wchar_t key;
		SuffixTreeNode<wchar_t> *item;
		bool more = iter.GetFirst(key,item);
		while(more)
		{
			collectWordContext(item,depth, ctx->str,depth, list,index);
			more = iter.GetNext(key,item);
		}
	}
}



//--------------------explict specialization for SegmentFragment----------------

template<>
void SuffixTree<SegmentFragment>::insert(SuffixTreeNode<SegmentFragment> * cur, SegmentFragment * suffix)
{
	cur->counter++;
	SegmentFragment * Next = 0;
	if(type == SuffixTree<SegmentFragment>::RIGHT_SUFFIX_TREE && (Next = suffix->next) != 0
		|| type == SuffixTree<SegmentFragment>::LEFT_SUFFIX_TREE && (Next = suffix->previous) != 0)
	{
		appendAsChildOrStringTail(cur, Next);
	}else
	{
		cur->endWithNullCounter++;
	}
}


template<>
void SuffixTree<SegmentFragment>::appendToPrefix(wchar_t * prefix, SegmentFragment state, wchar_t *newResult, int prefix_length)
{
	if(type == SuffixTree<wchar_t>::RIGHT_SUFFIX_TREE)
	{
		for(int i = 0; i < prefix_length; ++i)
		{
			newResult[i] = prefix[i];
		}
		for(int j = 0; j <= state.end - state.begin; ++j)
		{
			newResult[prefix_length+j] = state.begin[j];
		}
	}
	else
	{
		int strLength = state.end - state.begin;
		for(int j = 0; j <= strLength; ++j)
		{
			newResult[j] = state.begin[j];
		}
		for(int i = 0; i < prefix_length; ++i)
		{
			newResult[strLength+1+i] = prefix[i];
		}
	}

}
template<>
void SuffixTree<SegmentFragment>::collectWordContext(SuffixTreeNode<SegmentFragment> *node, int parent_depth, wchar_t* prefix, int prefixLength, 
													 WordContext<SegmentFragment>* list,int& index)
{
	int depth = parent_depth+1;
	
	SegmentFragment * frag = &node->state;
	int curLength = prefixLength + (frag->end - frag->begin) + 1;
	
	if(depth < minMumWordLength)
	{
		wchar_t * temp = new wchar_t[curLength];
		
		appendToPrefix(prefix,node->state,temp,prefixLength);

		AVL<SegmentFragment, SuffixTreeNode<SegmentFragment> *>::Iterator<SegmentFragment, SuffixTreeNode<SegmentFragment> *> iter(&node->children);
		SegmentFragment key;
		SuffixTreeNode<SegmentFragment> *item;
		bool more = iter.GetFirst(key,item);
		while(more)
		{
			collectWordContext(item,depth, temp,curLength,list,index);
			more = iter.GetNext(key,item);
		}
		delete [] temp;
	}
	else
	{
		WordContext<SegmentFragment> * ctx = &list[index++];

		//initial length
		ctx->length = curLength;
		
		//initial str
		ctx->str = new wchar_t[curLength];
		
		appendToPrefix(prefix,node->state,ctx->str, prefixLength);

		//remember current node reference
		ctx->treeNode = node;

		//travel to all node recursively
		AVL<SegmentFragment, SuffixTreeNode<SegmentFragment> *>::Iterator<SegmentFragment, SuffixTreeNode<SegmentFragment> *> iter(&node->children);
		SegmentFragment key;
		SuffixTreeNode<SegmentFragment> *item;
		bool more = iter.GetFirst(key,item);
		while(more)
		{
			collectWordContext(item,depth, ctx->str,curLength, list,index);
			more = iter.GetNext(key,item);
		}
	}
}
